package com.zjsru.oneDay202205;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/5/20
 *
 * 寻找右区间：
 * 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj>= endi ，且 startj 最小化 。
 * 看一个数组的左节点是否存在于其他数组中
 *
 * 返回一个由每个区间 i 的 右侧区间 在intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
 *
 * 输入：intervals = [[1,2]]
 * 输出：[-1]
 * 解释：集合中只有一个区间，所以输出-1。
 *
 * 输入：intervals = [[3,4],[2,3],[1,2]]
 * 输出：[-1,0,1]
 * 解释：对于 [3,4] ，没有满足条件的“右侧”区间。
 * 对于 [2,3] ，区间[3,4]具有最小的“右”起点;
 * 对于 [1,2] ，区间[2,3]具有最小的“右”起点。
 *
 */
public class findRightInterval {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] clone = new int[n][2];
        for (int i = 0; i < n; i++) {
            clone[i] = new int[]{intervals[i][0],i};
        }
        Arrays.sort(clone,(a,b) -> a[0] - b[0]);
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int l = 0, r = n -1;
            while(l < r){
                int mid = l + r >>1;
                if(clone[mid][0] >= intervals[i][1]) r = mid;
                else l =mid + 1;
            }
            ans[i] = clone[r][0] >= intervals[i][1] ? clone[r][1] : -1;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        findRightInterval findRightInterval = new findRightInterval();
        int[][] intervals = new int[][]{{3,4},{2,3},{1,2}};
        System.out.println(findRightInterval.findRightInterval(intervals));
    }
}
